c#

2024-07-17 12:41| 来源: 网络整理| 查看: 265

我是 C# 的新手，我有一个递归问题需要解决。我想在这个硬币找零问题中得到尽可能少的硬币。我已经为它调整了一个算法，但我需要返回一个 Change 类型的对象，它将包含尽可能少的组合。

我已经尝试实现一种算法，但我有所有可能的组合。

using System; using System.Collections.Generic; using System.Linq; // Do not modify change class Change { public long coin2 = 0; public long bill5 = 0; public long bill10 = 0; } class Solution { // Do not modify method signature public static Change OptimalChange(long s) { Change _change = new Change(); //To implement here return _change; } public static int GetCombinations(int total, int index, int[] list, List cur) { if (total == 0) { foreach (var i in cur) { Console.Write(i + " "); } Console.WriteLine(); return 1; } if (index == list.Length) { return 0; } int ret = 0; for (; total >= 0; total -= list[index]) { ret += GetCombinations(total, index + 1, list, cur); cur.Add(list[index]); } for (int i = 0; i < cur.Count(); i++) { while (cur.Count > i && cur[i] == list[index]) { cur.RemoveAt(i); } } return ret; } } public class Program { public static void Main() { Console.WriteLine("Hello Change"); int s = 41; /*Change m = Solution.OptimalChange(s); Console.WriteLine("Coins(s) 2euros :" + m.coin2); Console.WriteLine("Bill(s) 5euors :" + m.bill5); Console.WriteLine("Bill(s) 10euors :" + m.bill10); long result = m.coin2*2 + m.bill5*5 + m.bill10*10; Console.WriteLine("\nChange given =", + result);*/ Solution sol = new Solution(); int[] l = { 2, 5, 10 }; Solution.GetCombinations(s, 0, l, new List()); } }

预期结果

示例:可用的硬币是 {2,5,10}

-- 我有一个输入 12 --

程序应该返回

硬币 2 欧元:1 账单 5euors : 0 帐单 10euors : 1

-- 我的输入是 17 --

程序应该返回

硬币 2 欧元:1 账单 5euors : 1 帐单 10euors : 1

最佳答案

首先，了解递归的基本思想是什么:

如果我们可以不用递归解决问题，解决它并返回解决方案。如果不能，则将问题简化为一个或多个更小的问题，递归地解决每个更小的问题，然后组合这些解决方案来解决更大的问题。

其次，了解动态规划的基本思想是什么:

递归解决方案通常会多次重新计算同一个问题；有时存储解决方案比重新计算更有效。

好吧，让我们来解决你的问题。

// Do not modify change class Change { public long coin2 = 0; public long bill5 = 0; public long bill10 = 0; }

SCSS 。这个类很糟糕。修复它!

sealed class Change { public long Two { get; } public long Five { get; } public long Ten { get; } public Change(long two, long five, long ten) { this.Two = two; this.Five = five; this.Ten = ten; } public Change AddTwo() => new Change(Two + 1, Five, Ten); public Change AddFive() => new Change(Two, Five + 1, Ten); public Change AddTen() => new Change(Two, Five, Ten + 1); public long Count => Two + Five + Ten; public long Total => Two * 2 + Five * 5 + Ten * 10; }

从对您有帮助的数据结构开始，而不是伤害您的数据结构。

现在，让我们写一个递归函数:

public static Change OptimalChange(long s) { // Are we in the base case? Solve the problem. // If not, break it down into a smaller problem. }

基本情况是什么？实际上有两个。如果和为负则无解，如果和为零则有零解。

public static Change OptimalChange(long s) { if (s < 0) return null; if (s == 0) return new Change(0, 0, 0);

好吧，这是简单的部分。困难的部分是什么？好吧，如果有解决方案，那么它要么有 2，要么有 5，要么有 10，对吧？或者这三个都可以。那么让我们找出答案。

public static Change OptimalChange(long s) { if (s < 0) return null; if (s == 0) return new Change(0, 0, 0); Change tryTen = OptimalChange(s - 10)?.AddTen(); ...

你能从这里拿走吗？

当您拥有实现所需操作的数据结构时，看看问题变得容易多了？再次总是创建一个可以帮助您的数据结构。

下一个问题:这个算法效率很低。为什么？因为我们在不断地重新做我们已经做过的问题。假设我们正在评估 OptimalChange(22)。这会调用 OptimalChange(12)，OptimalChange(7) 又会调用 OptimalChange(5)。但是 OptionalChange(12) 也调用 OptimalChange(10)，它再次调用 OptimalChange(5)。答案没有改变，但我们重新计算。

那么，我们该怎么办？我们使用动态规划技术。有两种方法:

继续递归，记住递归函数。创建一个零钱数组，并随时填写。

但是等等，还有比性能问题更多的问题。我们每次把问题变小最多10，最小2，但是参数是long；它可能是数十亿或数万亿。如果我们有一个递归解决方案，我们会炸毁堆栈，如果我们有一个基于数组的解决方案，它会太大。

我们需要更聪明地在给定的可能输入范围内解决这个问题。仔细想想；我们能否在不使用递归、数组或长时间运行的循环的情况下分析地解决问题？或者，等价地，有没有一种方法可以快速将非常大的问题简化为小问题？然后可以用动态规划解决这个小问题。

作业问题总是这样请记住，您必须遵守好奖学金的规则。如果您在家庭作业解决方案中使用了来自 SO 的想法，您必须给予肯定。不这样做就是剽窃，如果你继续这样做，你会被一所体面的学校开除。

关于c# - 如何使用递归在 C# 中获得硬币找零问题的最少可能组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54708466/

【本文地址】

c#

c#

今日新闻

推荐新闻